package com.julius.design.suanfa.search;

/**
 * @author julius
 * @date 2021-11-04 下午 2:52
 * <p>
 *      给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；
 *      否则，返回 false 。
 *
 *      单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 *      同一个单元格内的字母不允许被重复使用。
 *      例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
 *
 *      链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
 * </p>
 */
public class SearchExist {


    /**
     * 搜索算法 矩阵相关
     *  使用DFS 深度优先搜索算法
     *
     *
     *    BCCED
     *       0  1  2  3
     *   0   B  B  C  E
     *   1   S  F  C  S
     *   2   A  D  E  E
     *
     *
     * @param board
     * @param word
     * @return
     */
    public static boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        //遍历矩阵的每一个节点作为开始节点
        for (int i = 0;i< board.length;i++){
            for (int j = 0;j < board[0].length;j++){
               if(dfs(board,words,i,j,0)){
                   return true;
               }
            }
        }
        return false;
    }

    /**
     * 深度优先搜索算法遍历矩阵
     * 沿着一个方向遍历（上 下  左  右）
     *
     * @param board 原矩阵
     * @param words 原字符串
     * @param i 矩阵节点的开始行
     * @param j 矩阵节点的开始列
     * @return
     */
    public static boolean dfs(char[][] board,char[] words,int i ,int j,int k){
        //结束本次遍历的条件 1. 矩阵相邻位置组成的字符串不word不同 2. i或者j出现了越界  这里要首先检验边界
        if(i >= board.length || i < 0 || j >= board[0].length  || j < 0 || words[k] != board[i][j] ){
            return false;
        }
        //在矩阵中找到了符合条件的相邻元素组成了word
        if(k == words.length - 1){
            return true;
        }
        //将访问过的元素标记，防止重复使用
        board[i][j] = '\0';

        //递归调用当前元素的上下左右位置 其中有一个方向符合要求即可
        boolean up  = dfs(board,words,i+1,j,k+1) || dfs(board,words,i-1,j,k+1) || dfs(board, words, i, j+1, k+1)|| dfs(board, words, i, j-1, k+1);
        //回溯，将矩阵上标记的元素复原
        board[i][j] = words[k];
        return  up;

    }


//    public boolean exist(char[][] board, String word) {
//        char[] words = word.toCharArray();
//        for(int i = 0; i < board.length; i++) {
//            for(int j = 0; j < board[0].length; j++) {
//                if(dfs(board, words, i, j, 0)) return true;
//            }
//        }
//        return false;
//    }
//    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
//        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
//        if(k == word.length - 1) return true;
//        board[i][j] = '\0';
//        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
//                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
//        board[i][j] = word[k];
//        return res;
//    }
}
